package io.github.handyang.algorithms.sort;

/**
 * 希尔排序更加适合大数组
 * <p>
 * 在 h==1 时，退化为插入排序
 */
public class ShellSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        int h = 1;
        //递增序列 ，希尔排序的性能与递增序列的选择息息相关
        while (h < arr.length / 3) h = h * 3 + 1;
        //更优秀的递增序列，提升 20%
        //1,5,19,41,109,209,505,929,2161,3905,8929,16001....


        //以下为错误代码（只调整了一个 h 数组）
//        while (h >= 1) {
//            for (int i = h; i < arr.length; i += h) {
//                for (int j = 0; j < i; j += h) {
//                    if (less(arr[i], arr[j])) {
//                        T t = arr[i];
//                        for (int k = i; k > j; k -= h) {
//                            arr[k] = arr[k - h];
//                        }
//                        arr[j] = t;
//                        break;
//                    }
//                }
//            }
//
//            h /= 3;
//        }

        while (h >= 1) {
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j >= h && less(arr[j], arr[j - h]); j -= h) {
                    swap(arr, j, j - h);
                }
            }

            h /= 3;
        }

    }
}
